Query optimizers in database management systems (DBMSs) can obtain an efficient execution plan for a given query. Many query optimizers use a transformation rule-based framework. Such query optimizers use transformation rules to generate different alternative plans for a query. Research has been done on identifying a set of transformation rules to be used by query optimizers, and the set of transformation rules has grown significantly over time. There has also been work centered on adding additional types of transformation rules to query optimizers. Some of the important classes of transformation rules include rules for pulling-up or pushing down a group-by operator, handling nested sub-queries, and commuting outer joins with joins.
There are at least two main kinds of transformation rules. Logical transformation rules transform logical operator trees into equivalent logical operator trees. Some examples of logical transformation rules include join commutativity and pushing group-by operators below join operators. On the other hand, implementation rules or physical transformation rules can transform logical operator trees into hybrid logical/physical trees. Example implementation rules include rules that transform a logical join operator into a hash join implementation. Some extensible optimizers also leverage the idea of transformation rules during the query rewrite phase to generate alternative logical representations of the input query.
Transformation rule-based query optimizers may use a top-down approach to query optimization. The query optimizer can be initialized with a logical tree of relational operators corresponding to an input database query. The query optimizer can transform the input logical tree into an efficient implementation operator tree to implement the query. For this purpose, transformation rules can be used to generate different alternative plans for executing a query. The set of transformation rules that may be available to the query optimizer can determine the search space of plans considered by the optimizer, and thus the set of rules can determine the quality and/or efficiency of the final plan.